Artificial intelligence, a subfield of computer science, attempts to understand the nature of intelligent action and construct computer systems capable of such action. One of the foundations of artificial intelligence is problem-solving methodology. For example, with a given representation of a task to perform, a method must be adopted that can guide the problem solver to accomplish the task. Acceptable problem-solving methodologies start with the problem to be solved and stress good representation using constraints to reduce the search space for feasible solutions.
A constraint is a relationship; a mathematical or logical expression over a set of constraint variables. The goal of a constraint system is to find the maximal subset of the legal values of a constraint variable, such that all of its associated constraints are satisfied. A variable X is a constraint variable if X can only take its value from a set D, the domain or legal values of X. Concentrating on constraints as part of a problem solving methodology allows the problem solver to uncover useful, interacting constraints or to propagate constraints that achieve global consistency through local computation.
In propagating constraints, the problem solver can find values for problem parameters that are consistent everywhere with some stipulated constraints. Propagation procedures operate independently on only a few parameters in a small set, and therefore are said to do local computation. When the constraints are satisfied everywhere, the consistency is said to be "global". Hence, the point of constraint propagation is to achieve global consistency through local computation.
The focus of a constraint satisfaction problem (CSP) is to derive the subset of its legal values (the constrained values) such that the constraints can be satisfied. Usually a CSP is solved through the process of constraint propagation. Constraint satisfaction has been used in circuit layout/analysis/simulation applications, and lately in scheduling and resource allocation problems.
Rule-based systems provide another problem-solving methodology that is popular in building artificial intelligence systems. One particularly important type of rule-based system is known as a deductive reasoning system. In a deductive reasoning system, statements known as "rules" have antecedents (or "if" parts) followed by consequences (or "then" parts). Rules are expressed in two different modes depending on use in the forward deduction or backward deduction paradigm. A forward-chaining rule represents a logical deduction based on the modus ponens, i.e. p,p.fwdarw.q,q. Backward deduction takes the form, q,p.rarw.q,p.
Operations management includes problems such as project planning and scheduling, resource allocation and optimization. These problems are common in both industrial and administrative domains and, these problems can be viewed as constraint satisfaction and deductive reasoning problems. In the field of operations research, for example, there are valuable analysis tools such as Performance Evaluation and Review Techniques (PERT), Critical Path Method (CPM), and the Gantt chart. Optimization procedures such as linear programming solve some important aspects of these problems. However, these tools assume a static problem definition and, for large-scale operations, take an excessive amount of time to compute the optimal solution.
In real life operations, dynamic changes, updates or perturbations, from minor to serious, are an immanent part of the problem. Before re-running an expensive optimization procedure, it is critical to analyze the down-line effects of these perturbations, process "what-if" scenarios, and check if simple heuristic rules will correct the problem. Heuristics such as task rearrangement, priority changes, first-in-first-out, inconsistent start or finish time shifts, constraint retraction, etc., have been the major source of expertise accumulated through experience. If a system existed that could rapidly use these heuristic tools together as a constraint satisfaction problem coupled with a deductive reasoning system, the user could easily and efficiently respond to dynamic changes. Such a system could process "what-if" scenarios in both a forward-chaining and backward-chaining framework. Furthermore, by combining constraint satisfaction with deductive reasoning, a much richer set of relationships would be possible for problems such as those of operations management.
There is, therefore, a need for a knowledge-processing environment that integrates constraint satisfaction and deductive reasoning methodologies.
There is a need for a system and method that provide a simple and straightforward rule-based framework to encode reasoning strategies.
There is a need for a method that combines a constraint system with a deductive reasoning system and allows the user to hypothetically visualize future scenarios by asking "what-if" questions.
There is a need for a system and method that provide a richer set of temporal relationships than the precedence relationships alone can provide for operations management problems.
There is a need for a system and method that are designed for modeling dynamic perturbations in the operations management domain.
There is a need for a system and method to encode expertise in relaxation strategies when situations arise that cause current operations to fail.